Optimization in ML

Perceptrons Review

• Inputs are feature values
• Each feature has a weight
• Sum is the activation: \(z=\mathrm{activation}_{w}(x)=\sum_{i}w_{i}{\cdot}f_{i}(x)=w{\cdot}f(x)\)
• Sigmoid function: \[ \phi(z)=\frac{1}{1+e^{-z}}=\begin{cases} 1,\lim_{z\to\infty} \\ 0, \lim_{z\to-\infty} \end{cases} \]
• Chose \(w\) by doing maximum likelihood estimation: \[ \max_{w}ll(w)=\max_{w}\sum_{i}\log\mathbb{P}(y^{(i)}|x^{(i)};w) \] with: \[ \begin{array}{c} \mathbb{P}(y^{(i)}=+1|x^{(i)};w)=\frac{1}{1+e^{-w{\cdot}f(x^{(i)})}} \\ \mathbb{P}(y^{(i)}=-1|x^{(i)};w)=1-\frac{1}{1+e^{-w}{\cdot}f(x^{(i)})} \end{array} \]
• Multiclass linear classification
  • Weight vector for each class \(w_{y}\)
  • Score (activation) of a class \(w_{y}{\cdot}f(x)\)
  • Prediction with the highest score wins ≙ \(y=\arg\max_{y}w_{y}{\cdot}f(x)\)
  • Use the same maximum likelihood estimation function but with: \[ \mathbb{P}(y^{(i)}|x^{(i)};w)=\frac{e^{w_{y^{(i)}}{\cdot}f(x^{(i)})}}{\sum_{y}e^{w_{y}}{\cdot}f(x^{(i)})} \]

Hill Climbing

• Start wherever
• Move to the best neighboring state
• If no neighbors are better than the current, quit
• Challenging with multiclass logistic regression b/c optimization is done over a continuous space ⟹ infinite neighbors

Gradients

• A gradient is a vector of partial derivatives with respect to each variable

• eg: \[ g(x,y)=x^{2}y \] \[ {\nabla}g=\begin{bmatrix} \frac{\partial{f}}{\partial{x}} \\ \frac{{\partial}f}{{\partial}y} \end{bmatrix}=\begin{bmatrix} 2xy \\ x^{2} \end{bmatrix} \] ## 1-D Optimization (Hill Climbing)

• Can sample random points \(w\) and take the \(w\) that maximizes the estimation

• Local hill climbing

  1. Evaluate \(g(w_{0}+h)\) and \(g(w_{0}-w)\)
  2. Update \(w\) to the maximum of the two values
  3. Repeat until local max found or some time limit is reached

• Evaluate derivative to find the direction to step in: \[ \frac{{\partial}g(w_{0})}{{\partial}w}=\lim_{h\to0}\frac{g(w_{0}+h)-g(w_{0}-h)}{2h} \]

n Dimensional Optimization (Gradient Ascent)

• Perform update in uphill direction for each coordinate

• The steeper the slope (the higher the derivative) the bigger the step for that coordinate

• eg given \(g(w_{1},w_{2})\) and hyperparameter for learning rate \({\alpha}\): \[ \begin{array}{c} w_{1}\leftarrow{w_{1}+{\alpha}*\frac{{\partial}g}{{\partial}w_{1}}(w_{1},w_{2})} \\ w_{2}\leftarrow{w_{2}+{\alpha}*\frac{{\partial}g}{{\partial}w_{2}}(w_{1},w_{2})} \end{array} \]

• Same as \[ {\nabla}_{w}g(w)=\begin{bmatrix} \frac{{\partial}g}{{\partial}w_{1}}(w) \\ \frac{{\partial}g}{{\partial}w_{2}}(w) \end{bmatrix} \] \[ w\leftarrow{w+{\alpha}*{\nabla}_{w}g(w)} \]

• Alg ∈ \(O(n)|_{n\,\coloneqq\,|\text{dimensions}|}\)

• \({\alpha}\) needs to be chosen carefully (generally s.t. update changes \(w\) by 0.1-1%)

Batch Gradient Ascent on the Log Likelihood Objective

\[ w\leftarrow{w+{\alpha}*\sum_{i}{\nabla}{\log}(\mathbb{P}(y^{(i)}|x^{(i)};w))} \] \[ \max_{w}ll(w)=\max_{w}g(w) \]

Stochastic Gradient Ascent on the Log Likelihood Objective

• Once gradient on one training example has been computed, might as well incorporate before computing next one \[ w\leftarrow{w+{\alpha}*{\nabla}{\log}(\mathbb{P}(y^{(j)}|x^{(j)};w))} \] \[ \max_{w}ll(w)=\max_{w}g(w) \]

Mini-Batch Gradient Ascent on the Log Likelihood Objective

• Gradient over small set of training examples (mini-batch) can be computed in parallel \[ \left.w\leftarrow{w+{\alpha}*\sum_{j\in{J}}\nabla\log\mathbb{P}(y^{(j)}|x^{(j)};w)}\right|_{J\;\coloneqq\;\text{random subset of training examples}} \] \[ \max_{w}ll(w)=\max_{w}\sum_{i}\log{\mathbb{P}(y^{(i)}|x^{(i)};w)} \] ## Deep Learning and Neural Networks

• Goal ≙ avoid manual feature design; allow computer to learn features too

• 

  • Different sets of weights for each individual summation
  • \(h\) ≙ hidden layers

• Finally: \[ y={\phi}(w_{1}h_{1}+w_{2}h_{2})=\frac{1}{1+e^{-(w_{1}h_{1}+w_{2}h_{2})}} \]

• Same as:

  • Helpful to keep track of the shapes of different vectors and arrays
    • \(x\) has shape \((1,\mathrm{dim}(x))\)
    • \(W_{layer1}\) has shape \((\mathrm{dim}(x),n)\)
    • \(h\) has shape \((1,n)\)
    • \(W_{layer2}\) has shape \((n,\mathrm{dim}(y))\)
    • \(y\) has shape \((1,\mathrm{dim}(y))\)
  • Can output an arbitrary \(\mathrm{dim}(y)\) length vector
  • Layer 1 has weight matrix with shape (dim(x), n). These are the weights for n neurons, each taking dim(x) features as input. This transforms a dim(x)-dimensional input vector into an n-dimensional output vector.
  • Layer 2 has weight matrix with shape (n, dim(y)). These are the weights for dim(y) neurons, each taking n features as input. This transforms an n-dimensional input vector into a dim(y)-dimensional output vector.

• Multi-layer Neural Network: \[ \left.z_{i}^{(k)}=g\left(\sum_{j}W_{i,j}^{(k-1,k)}z_{j}^{(k-1)}\right)\right\vert_{g\;\coloneqq\;\text{nonlinear activation function}} \]

Batch Sizes

- Multilayer network with batches: